# source:https://leetcode.cn/problems/shortest-subarray-with-or-at-least-k-ii/  位运算 滑窗
class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = inf
        i = 0
        count_or = 0
        d = defaultdict(int)
        for j, v in enumerate(nums):
            t = 0
            while v >> t:
                if (v >> t) & 1:
                    d[1 << t] += 1
                t += 1
            
            count_or |= v
            while i <= j and count_or >= k:
                ans = min(ans, j-i+1)
                t = 0
                while nums[i] >> t:
                    if (nums[i] >> t) & 1:
                        d[1 << t] -= 1
                        if d[1 << t] == 0:
                            count_or -= 1<<t 
                    t += 1
                i += 1
            # print(i, j, count_or, ans)
        return ans if ans < inf else -1

# source:https://leetcode.cn/problems/count-number-of-nice-subarrays/ 定长滑窗
class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        ans = 0
        i = 0
        oven = []
        for ind, v in enumerate(nums):
            if v & 1:
                oven.append(ind)

        for i in range(len(oven)-k+1):
            ans += ((oven[i]-(oven[i-1] if i > 0 else -1)) * ((oven[i+k] if i+k < len(oven) else len(nums)) - oven[i+k-1]))
        return ans